
\documentclass[11pt]{article}
\newtheorem{define}{Definition}
\newcommand{\leftexp}[2]{{\vphantom{#2}}^{#1}{#2}}
%\newcommand{\F}{{\mathbb{F}}}
%\usepackage{psfig}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{fullpage, color}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\def\Ex{ {\mathbb{E}}}
\def\I{ {\mathbb{I}}}

\begin{document}
\input{preamble.tex}


\def\A{ {\mathcal{A}}}
\def\D{ {\mathcal{D}}}
\def\E{ {\mathbb{E}}}
\def\P{ {\mathcal{P}}}
\def\Rd{ {\mathcal{R}}}     % For distribution R.
\def\code{ {\mathrm{code}}}
\def\cost{ {\mathrm{cost}}}
\def\supp{ {\mathrm{supp}}}
\def\union{ {\bigcup}}

%{lecture number}{lecture date}{Anand Louis}{Your name}
\lecture{10}{Sept. 20, 2012}{Anand Louis}{Pinar Delul, Pawan Nagesh}

%%%% body goes in here %%%%

In this lecture we'll talk about graph expansion and relate it to the spectral properties of the adjacency matrix of a graph.


\begin{definition}
 Let $G$ be a $d$-regular graph $G(V,E)$ and  $S \subseteq V$ be a set of vertices of $G$. Let  
$\Phi(S)= \frac{|E(S, \bar{S})|}{d\cdot|S|}\in (0,1)$, (where $|E(S, \bar{S})|$ indicates the number of edges between $S$ and ${\bar S}$ and $|S|$ is the number of vertices in $S$.)
Let $\Phi(G)=\min_S \Phi(S)$.

\end{definition} 

\begin{definition}(Expander Graph)
$G$ is an $\alpha$-expander if 
$\Phi(G)\geq \alpha$.
\end{definition}

Can one determine the expansion of a graph efficiently? Notice that the trivial algorithm would be to run through all subsets $S$, but this gives an exponential time algorithm. While deciding if an expander is an $\alpha$-expander or not is coNP hard, there is an efficient algorithm that can decide if $G$ is an $\alpha$-expander or not an $\alpha^2$-expander.


\begin{theorem}\label{thm:1}
There is a polynomial time algorithm that can decide if a given graph $G$ is an $\alpha$-expander or not an $\alpha^{2}$ - expander.
\end{theorem}


Let $A$ be adjacency matrix of $G$ and consider  the Laplacian matrix
  $L= I - \frac{A}{d}$, 
 where  $I$ is the identity.
 Since $G$ is $d$ regular, the smallest eigenvalue of $L$ is $\lambda_1=0$ (so $L$ is a PSD matrix). Let $\lambda_2$ be the second smallest eigenvalue. 
  
  \begin{theorem}(Cheeger's inequality)\label{thm:2}
$\frac{\lambda_{2}}{2} \leq \Phi(G) \leq \sqrt{2\lambda_{2}}$
  \end{theorem}

Note that Theorem \ref{thm:2} implies Theorem \ref{thm:1}. We will next show Theorem \ref{thm:1}.


\begin{proof} We start by showing the first inequality. It suffices to show  $\lambda_2/2\leq  \frac{|E(S, \bar{S})|}{d\cdot|S|}, ~\forall S$ where $|S| \leq \frac{n}{2}$.
We know that $\lambda_2=\min_{x\perp {\bf 1}}\frac{x^{t}L x}{x^{t}x}$ (since ${\bf 1}$ is the eigenvector corresponding to $\lambda_1$).
Let $I_S$ be the indicator vector of the set $S$ with $|S|\leq n/2$. Let $x=I_S-\frac{|S|}{n}{\bf 1}$.       
%        $S^{(i)}$ = 1 if i belongs to  S, 0 otherwise.
% Clearly this is not orthogonal to all 1's vector.
%  = $\bot 1s - <\bot 1s, \frac{\bot 1s}{\sqrt n}>.\frac{\bot}{\sqrt n}$.
%       
%  = $\bot 1s - \frac{|S|}{n}$  
%  
%  
 So $x_i =  1 - \frac{|S|}{n}$  if $i$ belongs to $S,$
 else $x_i =  \frac{-|S|}{n}$. Observe that $\langle x,{\bf 1}\rangle=(1 - \frac{|S|}{n})\cdot |S|-\frac{|S|}{n}(n-|S|)=0$ so $x\perp {\bf 1}$.
Note that $x^t L x=\frac{\sum_{i\sim j} (x_i-x_j)^2}{d}$ and that $x^tx=\sum x_i^2$, and further that 
  that $\sum_{i\sim j} (x_i-x_j)^2=|E(S,{\bar S})|$.
Also $\sum x_i^2=(\frac{n-|S|}{n})^2|S|+(n-|S|)(\frac{|S|}{n})^2=\frac{(n-|S|)(|S|)}{n}\geq |S|/2$. Therefore $\lambda_2\leq \frac{x^{t}L x}{x^{t}x}=\frac{2 |E(S,{\bar S})|} {(d|S|)}, $ and the first part of the theorem is proved.

  
 The 2nd inequality is harder to show.
It is enough to show that  $ \exists  S \text{such that }  \Phi(S)\leq \sqrt{2\lambda{2}}$.
 {Let $x$ be the eigenvector of $L$ corresponding to $\lambda_{2}$} and assume it has at most $n/2$ positive entries (if not, the same argument works for $-x$).
 Let 
$y_{i} =\begin{cases}
&x_{i} \text{ if } x_{i} > 0 \\
&0 \text{ otherwise} 
\end{cases}
$  

We will find the set $S$ by the following algorithm:

\begin{enumerate}
\item Sort the entries of $y$ in decreasing order, say $y_{1} \geq y_{2} \geq \ldots \geq y_m>0>\ldots$
\item Let $S_{i}$ be the set consisting of the first $i$ vertices in this ordering.
\item Output the set $S=S_{i}$ that has the least $\Phi(S_{i})$.
\end{enumerate}

To complete the proof it is enough to show the following 2 lemmas.


\begin{lemma}\label{lem:XX}
    \begin{align*}
\frac{\sum_{i \sim j } |y_{i}^{2} - y_{j}^{2}|}{ d\sum_{i}y_{i}^{2}} \leq \sqrt{2\lambda_{2}}
  \end{align*}
\end{lemma}

\begin{lemma}\label{lem:X}
    \begin{align*}
\Phi(S) \leq \frac{\sum_{i \sim j }|y_{i}^{2} - y_{j}^{2}|}{d \sum_{i}y_{i}^{2}}\\
  \end{align*}
\end{lemma}



\begin{proof}[of Lemma \ref{lem:XX}]
We have that $(I - \frac{A}{d})x = \lambda_{2}x$, implying 
$x - \frac{A}{d}x = \lambda_{2}x$, and so 
$(1 - \lambda_{2})x = \frac{A}{d}x$.
Therefore, a case analysis implies  $\frac{A}{d}y \geq (1-\lambda_{2})y \geq (1-\lambda_{2})x$ (the notation is slightly abusive, but it simply means that the inequality holds pointwise, for any two corresponding indices in the two vectors), and further $(I-A/d)y\leq \lambda_2 y$  and so $\frac{y^t L y}{y^t y}\leq \lambda_2$.


% \begin{definition}[Case 1]
% 
% \begin{align*}
% & x_{i} = 0,  x_{i} = y_{i}\\
% & \frac{A}{d} y = (1 - \lambda_{2})y
% \end{align*}
% 
% \end{definition}
% 
% \begin{definition}[Case 2]
% \begin{align*}
% &x_{i} < 0, y_{i} = 0\\
% &\frac{A}{d} y \geq (1 - \lambda_{2})y\\
% &y^T(I - \frac{A}{d})y \leq y^T \lambda_{2}y
As before, it follows that 
$\frac{y^t L y}{y^t y}=\frac{\sum_{i \sim j}(y_{i}-y_{j})^{2}}{d \sum_{i}y_{i}^{2}} \leq \lambda_{2}.$
%\end{definition}

We have that\begin{align*}
&\sum_{i \sim j}|y_{i}^2-y_{j}^2| = \sum_{i \sim j}|y_{i}-y_{j}||y_{i}+y_{j}|\\
&\leq \sqrt{\sum_{i \sim j}(y_{i}-y_{j})^{2}} \cdot \sqrt{\sum_{i \sim j}(y_{i}+y_{j})^{2}}\\
& \leq \sqrt{{\sum_{i \sim j}(y_{i}-y_{j})^{2}}}\cdot \sqrt{\sum_{i \sim j} 2(y_i^2+y_j^2)}\\
&= \sqrt{{\sum_{i \sim j}(y_{i}-y_{j})^{2}}}\cdot\sqrt{2d \sum_{i}y^2_{i}},
\end{align*}
(where we applied Cauchy-Schwartz twice and used the $d$-regularity of the graph).
So 
\begin{align*}
& \frac{\sum_{i \sim j}|y_{i}^2-y_{j}^2| }{d \sum_{i} y_{i}^2} \leq\frac{ \sqrt{\sum_{i \sim j}(y_{i}-y_{j})^{2}}\cdot\sqrt{2d\sum y_{i}^2}}{d\sum y_{i}^2}\\
& = \sqrt{\frac{2\sum_{i \sim j}(y_{i}-y_{j})^{2}}{d\sum y_{i}^2 }}\leq \sqrt{2\lambda_2}
\end{align*}
\end{proof}

\begin{proof}[of Lemma \ref{lem:X}]

Assume now for contradiction that $\forall i$, $\Phi(S_i)=\frac{|E(S_i, {\bar S_i}|)}{d|S_i|}>\beta$, where $\beta=\frac{\sum_{i\sim j} |y_i^2-y_j^2|}{d\sum_i y_i^2}$. So, $|E(S_i, {\bar S_i})|>d|S_i|\beta=d \cdot i\cdot \beta.$

We have 
\begin{align*}
&\sum_{i\sim j} |y_i^2-y_j^2|=\sum_{i < j, i\sim j}y_{i}^2 - y_{j}^2 = 
\sum_{i<j,i \sim j}\sum_{t=i}^{j}(y_{i}^2 - y_{i+1}^2 )\\
&= \sum_{i=1}^m (y_{i}^2 - y_{i+1}^2) \cdot |E(S_{i}, \bar{S_{i}})|\\
&> \sum_{i=1}^m (y_{i}^2 - y_{i+1}^2) d i \beta\\
&=d\beta(\sum_{i=1}^m (i y_{i}^2 -i y_{i+1}^2))\\
&=d\beta \sum_{i=1}^{m} y_i^2,
\end{align*}

(we used that if $j\sim i$ and $i<j$ the edge $(ij)$ cannot be in $S_i$ and the assumption that $|E(S_i, {\bar S_i}|>d i\beta$.) 
The above derivation implies $\frac{\sum_{i\sim j} |y_i^2-y_j^2|}{d\sum y_i^2}=\beta>\beta$, a contradiction. This implies that $\exists  S_{i}$  s.t. $\Phi(S_{i}) \leq \beta $ and concludes the proof of the lemma and of Cheeger's inequality
\end{proof}
\end{proof}

\end{document}




